package com.cskaoyan.javase.recursion._1basic;

/**
 * 引例：
 *  使用循环和递归计算N（N>=1）的阶乘（factorial）
 *
 *  先考虑使用循环计算
 *  使用循环,优先去找循环的循环体语句
 *  n! = n * (n-1) * (n-2) * ... * 1;
 *  n个数相乘,但是每乘一次就减1
 *  最后搞明白循环的次数,循环基本上就可以写出来了.
 *
 *  用递归思考问题又是什么样的过程呢?
 *  递归的思想就是分解问题的思想:
 *      1.把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。(递归体)
 *      2.当子问题规模足够小的时候，就可以直接得到小规模问题的解。(递归的出口)
 *      3.然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。
 *
 * n! = n * (n-1)! (递归体)
 * (n-1)! = (n-1) * (n-2)!
 * ...
 * 以上分解的过程肯定不是无限的
 * 当n = 1时,1! = 1 (递归的出口)
 *
 * 不难发现递归的优点是：
 *      1.递归的代码会非常简洁，这是最直观的。
 *      2.人在解决问题的时候，都会下意识的分解问题。
 *          递归的思想很符合人的思维，用递归求解一个问题的思路很容易被人理解。
 *      3.接第二条，一旦能够找到分解问题的思路，递归会非常好用。
 *
 * 比起优点,递归的缺点更明显:
 *      1.栈溢出错误警告！递归很危险，一旦栈溢出是严重错误！
 *      2.不用递归时，往往一个方法就能解决问题。而递归会调用多个方法，占用大量栈内存.(空间复杂度很低)
 *          且明显存在大量重复计算，效率低。
 *          也就是说，使用递归求解一个问题，时间和空间复杂度都不占优势，既占用空间效率还低。
 *
 *  但是递归还是很有用的,在某些场景下,不使用递归,几乎不太好想解决方法.
 *
 * @since 11:10
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoop(16));
        System.out.println(factorialRecursion(16));
    }

    public static long factorialRecursion(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return n * factorialRecursion(n - 1);
    }

    public static long factorialLoop(int n) {
        // 定义结果
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}
